home *** CD-ROM | disk | FTP | other *** search
/ Shareware Super Platinum 8 / Shareware Super Platinum 8.iso / mac / PROGTOOL / KAFSORT.ZIP;1 / SORT.C < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-28  |  16.1 KB  |  490 lines
  1. /***********************************************************************
  2.  * SORT.C - An array of functions to sort data.
  3.  *
  4.  *  VERSION 1.0   3/21/92
  5.  *  Version 1.1   8/2/92 Change fill to use FF vs. 0 to handle null strings
  6.  *  Version 1.2  10/29/92 Changed to put sort tag into accessible field
  7.  *                        when fetching records. 'fetchtag'
  8.  *  Version 1.3   4/7/93  Changed to use Temporary Files to allow
  9.  *                        multi-user activity with no clashes.
  10.  ***********************************************************************/
  11. #include <stdio.h>
  12. #include <stdlib.h>
  13. #include <string.h>
  14. #include <fcntl.h>
  15. #include <io.h>
  16. #include <sys\stat.h>
  17. #include <alloc.h>
  18.  
  19. /** DEFINITIONS **/
  20.  
  21. #define TRUE 1
  22. #define FALSE 0
  23.  
  24. #define ESC 27
  25.  
  26. #define SMMAX   51200    /* bytes to ask for to sort */
  27. #define SMMIN   10240    /* Minimum bytes acceptable */
  28.  
  29. #define STAGMAXLEN  80   /* Maximum Sort Tag Allowed */
  30.  
  31. #define SORTOK 0        /* Sort Status is O.K. - No error */
  32. #define OK 0
  33. #define FETCHEND -1     /* End of Fetch */
  34. #define SORTERR -2      /* Sort Error */
  35.  
  36.  
  37.  
  38. /****** -------- SORT ERROR CODES ------------ ******
  39.  
  40. ERROR codes are found in the Global Variable sorterror
  41.  
  42. 1 = InitSort failed - Not enough memory
  43. 2 = Unable to Open/Create Sort File
  44. 3 = ERROR Writing to Sort File
  45. 4 = Unable to Open/Create Merge File
  46. 5 = Not enough memory for Merge
  47. 6 = Error reading Sort Tag for Merge
  48. 7 = Error Writing to Merge File
  49. 8 = Error Reading Fetch File
  50. 9 = Sort Tag Length Exceeds Maximum
  51.  
  52. *****************************************************/
  53.  
  54.  
  55. initsort(int taglength);
  56. void endsort();
  57. sort(char *ss, long srpos);
  58. initfetch();
  59. long fetch();
  60. fbread(unsigned rsize);
  61. sbwrite();
  62. merge();
  63. mbwrite(unsigned tagcount);
  64. bktfill(int bnum);
  65. zerobuf(char *bptr, unsigned count);
  66.  
  67.  
  68. /****************************************************************
  69.  **  GLOBAL VARIABLES - Accessible in applications 
  70.  ****************************************************************/
  71. int sorterror;     /* Contains Sort Error Code when Error */
  72. char fetchtag[STAGMAXLEN+1]; /* Area for Tag */
  73.  
  74. /******************************************************
  75.  * THE FOLLOWING VARIABLES ARE NOT FOR EXTERNAL ACCESS
  76.  ******************************************************/
  77. char sortfile[81];   /* Temporary File Name */
  78. char mergefile[81];  /* Temporary File Name */
  79.  
  80. int staglen;      /* Length of ASCII Sort Tag */
  81. char *sbuf;      /* sort Buffer Pointer */
  82. size_t sbsize;     /* size of the Sort Buffer */
  83. unsigned bufmax;     /* Max Number of tags that will fit into sort buffer */
  84. unsigned mbufmax;   /* Max Tags fitting into merge buffer */
  85. long sortcount;  /* Number of tags sorted */
  86. long fetchcount; /* Count of tags fetched */
  87. int sblocks;     /* Number of sort blocks */
  88. unsigned bufcount;   /* count of items in buffer */
  89.  
  90. int mfh;         /* Merge file Handle */
  91. int sfh;         /* Sort File Handle */
  92. int sbfflag;     /* Sort Buffer file flag */
  93. long sbfptr;      /* Sort File Pointer */
  94. char *stptr;     /* Sort Tag Pointer */
  95. long *lptr;      /* Pointer to Long */
  96. unsigned *uptr;  /* Pointer to Unsigned */
  97.  
  98. long fetch();    /* Fetch returns a long value */
  99. size_t fbsize;   /* Size of a Fetch Buffer */
  100.  
  101. int tpsize = sizeof(long);   /* Get the size of a tag pointer */
  102. int mcountsize = sizeof(unsigned);  /* Size of the merge counter value */
  103. int tagsize;     /* Size of a sort/merge tag (tag+pointer) */
  104. size_t bktsize;     /* Size of the bucket in total */
  105.  
  106. char *bktptr;    /* Pointer into the merge buckets */
  107. int buckets;   /* Number of Merge buckets (one for each sort block) */
  108. char *mrgbuf;     /* Merge buffer start address */
  109. char *mbptr;      /* Merge buffer pointer */
  110. size_t mbsize;    /* Merge buffer size */
  111.  
  112. /***************************************************************
  113.  * INITSORT - Initialize the Sort
  114.  ***************************************************************/
  115. initsort(int taglength)
  116. {
  117.    if(taglength > STAGMAXLEN)
  118.       {
  119.       sorterror = 9; /* Indicate Tag size too big */
  120.       return(SORTERR);
  121.       }
  122.    sorterror = 1;          /* Init Sort Error */
  123.    staglen = taglength;     /* Set the Sort Tag Size */
  124.    if(sbuf) free(sbuf);  /* Free any existing buffer */
  125.    sbsize = SMMAX;       /* Go for maximum memory */
  126.    while(sbsize > SMMIN)
  127.       {
  128.       sbuf=malloc(sbsize);
  129.       if(sbuf) break;     /* Leave loop when allocated */
  130.       sbsize -= 2048;     /* Reduce our attempt */
  131.       }
  132.    if(!sbuf) return(SORTERR);  /* No Sort Space */
  133.    zerobuf(sbuf,sbsize);    /* Zero the sort buffer */
  134.    stptr = sbuf;             /* Point to the sort buffer */
  135.    sortcount=0;
  136.    bufcount=0;
  137.    sblocks = 0;
  138.    mfh = NULL;
  139.    sbfflag = FALSE;
  140.    tagsize = staglen + tpsize; /* Size of a sort/merge tag (tag+pointer) */
  141.    bufmax = sbsize / tagsize;  /* See how many will fit */
  142.    return(SORTOK);
  143. }
  144.  
  145.  
  146. /******************************************************************
  147.  * ENDSORT - End a sort function
  148.  ******************************************************************/
  149. void endsort()
  150. {
  151.    free(sbuf);
  152.    sbuf = NULL;
  153.    sbsize=0;
  154.    sortcount=0;
  155.    if(sfh!=NULL)
  156.       {
  157.       close(sfh);         /* close the Sort Blocks file */
  158.       remove(sortfile);   /* Delete the Sort Blocks File */
  159.       }
  160.    if(mfh!=NULL)
  161.       {
  162.       close(mfh);  /* close the Sort Blocks file */
  163.       remove(mergefile);   /* Delete the Sort Blocks File */
  164.       }
  165. }
  166.  
  167. /*******************************************************************
  168.  * SORT - Accept a tag and sort it
  169.  *        If a tag exceeds the max sort tag length it will be truncated
  170.  *******************************************************************/
  171. sort(char *ss, long srpos)
  172. {
  173.    strcpy(stptr, ss);  /* Copy in the Sort Tag */
  174.    stptr += staglen;  /* Move the Pointer */
  175.  
  176.    lptr = (long *) stptr;   /* Set pointer to accept long value */
  177.    *lptr = srpos;
  178.  
  179.  
  180.    stptr += tpsize;  /* Move pointer */
  181.    sortcount++;
  182.    bufcount++;
  183.    if(bufcount >= bufmax)  /* Write out the Sort Buffer, it's full */
  184.       {
  185.       if(sbwrite()!=SORTOK) return(SORTERR);
  186.       stptr=sbuf;   /* Reset the pointer */
  187.       bufcount=0;
  188.       }
  189. return(SORTOK);
  190. }
  191.  
  192. /********************************************************************
  193.  * INITFETCH - Initialize the fetch
  194.  ********************************************************************/
  195. initfetch()
  196. {
  197.    fbsize = bufmax * tagsize;   /* Size of Fetch Buffer Reads */
  198.    if(mfh != NULL)
  199.       {
  200.       sorterror = 9;
  201.       if(lseek(mfh,0L,0)==-1L) return(SORTERR); /* Rewind Merge File for Fetch */
  202.       if(fbread((unsigned)fbsize)!=SORTOK) return(SORTERR);
  203.       }
  204.    stptr=sbuf;
  205.    fetchcount=0;
  206.    bufcount=0;
  207.    if(sfh!=NULL)
  208.       {
  209.       close(sfh);  /* close the Sort Blocks file */
  210.       remove(sortfile);   /* Delete the Sort Blocks File */
  211.       }
  212.  return(SORTOK);
  213. }
  214.  
  215. /**********************************************************************
  216.  * FETCH - Fetch the next sorted record's pointer
  217.  **********************************************************************/
  218. long fetch()
  219. {
  220.    long srpos;
  221.  
  222.    if(fetchcount==sortcount) return(FETCHEND);
  223.    strcpy(fetchtag, stptr);  /* Copy the Fetch Tag for User */
  224.    stptr += staglen;
  225.    lptr = (long *) stptr;
  226.    srpos=*lptr;
  227.    stptr += tpsize;  /* Move pointer */
  228.    fetchcount++;
  229.    bufcount++;
  230.    if(bufcount >= bufmax)
  231.       {
  232.       if(fbread((unsigned) fbsize)!=SORTOK) return(SORTERR);
  233.       stptr=sbuf;
  234.       bufcount=0;
  235.       }
  236.    return(srpos);
  237. }
  238.  
  239. /**********************************************************************
  240.  * FBREAD - Read in a new portion of fetch tags into the buffer.
  241.  **********************************************************************/
  242. fbread(unsigned rsize)
  243. {
  244.    zerobuf(sbuf,sbsize);  /* Zero the Buffer 1st */
  245.    sorterror = 8;
  246.    if(read(mfh,sbuf,rsize)==-1l) return(SORTERR);
  247.    return(SORTOK);
  248. }
  249.  
  250. /***********************************************************************
  251.  * SBWRITE - Write out a sort buffer full of tags
  252.  *   Tags are written to a section of the sortfile.
  253.  *
  254.  ***********************************************************************/
  255. sbwrite()
  256. {
  257.    char *sfname;
  258.  
  259.    if(!sbfflag)
  260.       {
  261.       sorterror = 2;
  262.       if((sfname=tempnam("\\temp","SORT"))==NULL) return(SORTERR);
  263.       strcpy(sortfile,sfname);
  264.       free(sfname);
  265.  
  266.       sfh = open(sortfile,
  267.          O_RDWR | O_BINARY | O_DENYNONE | O_CREAT | O_TRUNC,
  268.             S_IREAD | S_IWRITE); /* Get file Handle */
  269.       if(sfh == -1) return(SORTERR);
  270.  
  271.       sbfflag = TRUE;  /* Sort File is now Open */
  272.       sbfptr = 0;
  273.       }
  274.    qsort(sbuf, (size_t) bufcount, (size_t) tagsize, stricmp);
  275.    lseek(sfh, sbfptr, 0);  /* Seek to position */
  276.    sorterror = 3;
  277.    if(write (sfh, sbuf,sbsize) != sbsize) return(SORTERR);
  278.    sblocks++;
  279.    sbfptr += sbsize;  /* Move the File Pointer */
  280.    zerobuf(sbuf, sbsize);        /* Zero the Sort Buffer */
  281.    return(SORTOK);
  282. }
  283.  
  284. /** =============================================================
  285.  
  286. The merge step passes
  287. BACK POINTERS DIRECTLY FROM THE MERGE FUNCTION.  I.E. 20 BUCKETS FROM 20
  288. BLOCKS ARE HELD IN MEMORY AND KEEP BEING REFILLED.
  289.  
  290.  
  291. SBLOCKS are written to disk as 'sbsize' records.  Merge has pointers to each
  292. block.  When a block's pointer reaches the next block's start point it has
  293. exhausted that block.
  294.     bptr[1] == bptr[2] = Block Exhausted
  295.     (*bptr[1] == -1) = No more records here
  296.  
  297. ALL DATA SORTED (SORT TAGS) ARE ALWAYS CHARACTER.
  298. This means that -1 for a sort tag means end of tags this block.
  299.  
  300.  
  301. ** ================================================================**/
  302.  
  303. /************************************************************************
  304.  * MERGE - Merge the sorted.
  305.  *    If only 1 sort block no need to write to a file. Sort it in memory.
  306.  ***********************************************************************/
  307. merge()
  308. {
  309.  
  310.    unsigned bktarea;
  311.    int i, cbucket;      /* ChosenBucket # */
  312.    char *ctag;          /* Chosen Tag */
  313.    long rpos;           /* Record Position Value */
  314.    char *sfname;
  315.  
  316.  
  317.    stptr = sbuf;     /* Be sure the pointer is pointed to the Sort Buf for Fetch */
  318.  
  319.    /*
  320.     * For The First scenario there is only the sortblock still in
  321.     * memory.  All we have to do is sort it and ready for the Fetch.
  322.     */
  323.    if(sblocks == 0)
  324.       {
  325.       qsort(sbuf,(size_t) bufcount,(size_t) staglen + sizeof(long), stricmp);
  326.       bufcount = 0;
  327.       if(initfetch()==SORTERR) return(SORTERR);
  328.       return(SORTOK);
  329.       }
  330.  
  331.    /*
  332.     * Open the Merge File Now
  333.     */
  334.     sorterror = 4;
  335.     if((sfname=tempnam("\\temp","MERGE"))==NULL) return(SORTERR);
  336.     strcpy(mergefile,sfname);
  337.     free(sfname);
  338.  
  339.     mfh = open(mergefile,
  340.          O_RDWR | O_BINARY | O_DENYNONE | O_CREAT | O_TRUNC,
  341.             S_IREAD | S_IWRITE); /* Get file Handle */
  342.       if(mfh == -1) return(SORTERR);
  343.  
  344.  
  345.    /*
  346.     * Scenario TWO says there have been 1 or more blocks written to disk.
  347.     * Now we must merge the blocks to be ready to fetch.  If there's data
  348.     * in the sort buffer write it out.  Then split the sort buffer into two
  349.     * sections.
  350.     *  Section 1 = MergeBuckets (sbuf=the start  mbktptr=the pointer)
  351.     *  Section 2 = MergeBuffer (mrgbuf=the start mbptr=the pointer)
  352.     */
  353.  
  354.    if(bufcount)
  355.       {
  356.       if(sbwrite()==SORTERR) return(SORTERR);
  357.       }
  358.    zerobuf(sbuf, sbsize);   /* Zero the whole buffer */
  359.    buckets = sblocks;                /* The number of merge buckets needed */
  360.    bktsize = tagsize + mcountsize;   /* Size of the bucket in total */
  361.    bktarea = bktsize * buckets;       /* Size of the buckets area */
  362.    mbsize = sbsize - bktarea;     /* What's left is merge buffer */
  363.    mbufmax = mbsize / tagsize;         /* Number to fit in merge buffer */
  364.    mrgbuf = sbuf + bktarea;        /* Pointing to merge buffer */
  365.    mbptr = mrgbuf;
  366.    bufcount = 0;                      /* Zero the counter */
  367.    sorterror = 5;
  368.    if(mbufmax < 1) return(SORTERR);
  369.  /*
  370.   * Now fill in the initial buckets.  The Bucket format is as follows:
  371.   *  SortBlockCount(BUFMAX) - file pointer - TAG - Tag pointer
  372.   */
  373.   for(i=0; i<buckets; i++)
  374.    {
  375.     bktptr = sbuf + (i * bktsize);  /* Point to the bucket */
  376.     uptr = (unsigned *) bktptr;     /* Ready to accept an unsigned value */
  377.     *uptr = 0;                /* counter of the Sort Block */
  378.     if(bktfill(i)==SORTERR) return(SORTERR);   /* Fill in the bucket while we're here */
  379.    }
  380.  
  381.  /*
  382.   * Now all buckets are set up and the first element should be in each bucket.
  383.   * The next step is to Find the lowest element and move it to the buffer.
  384.   * When an element is moved to the buffer it will also be replaced in the
  385.   * bucket.  When the merge buffer fills it will be written to disk to the
  386.   * final sorted file.
  387.   */
  388.   while(TRUE)
  389.    {
  390.    cbucket = -1;   /* Clear the Selection */
  391.    ctag = NULL;    /* Null the pointer */
  392.  
  393.    for(i=0; i<buckets; i++)
  394.       {
  395.       bktptr = sbuf + (i * bktsize);  /* Point to the bucket */
  396.       uptr = (unsigned *) bktptr;     /* Ready to accept an unsigned value */
  397.       bktptr += mcountsize;           /* Point it at TAG */
  398.  
  399.       /* Skip bucket if depleted or No more tags here */
  400.       if(*uptr < bufmax+1 && bktptr[0] != -1)
  401.          {
  402.      if(ctag==NULL)  ctag = bktptr;         /* Starting point for compare */
  403.      if(stricmp(ctag, bktptr)>=0)
  404.            {
  405.            ctag = bktptr;   /* New Lower value */
  406.            cbucket = i;
  407.            }
  408.          }
  409.       }
  410.    if(cbucket < 0) break;  /* No more tags We're DONE !! */
  411.  
  412.    /*
  413.     * We have the lowest tag pointed to by ctag.  Move it to the buffer
  414.     */
  415.    strcpy(mbptr, ctag);  /* Copy the tag in */
  416.    ctag += staglen;      /* Move to the record pointer value */
  417.    mbptr += staglen;     /* Ditto in the merge buffer */
  418.  
  419.    lptr = (long *) ctag;  /* Point at record position */
  420.    rpos = *lptr;         /* And get the value */
  421.  
  422.    lptr = (long *) mbptr;   /* Ready to get long value */
  423.    *lptr = rpos;            /* Get record pointer */
  424.    mbptr +=tpsize;      /* Point to next tag area */
  425.  
  426.    if(bktfill(cbucket)==SORTERR) return(SORTERR);
  427.    bufcount++;
  428.    if(bufcount >= mbufmax)
  429.       {
  430.       mbwrite(bufcount);       /* Write out the merge buffer */
  431.       mbptr = mrgbuf;  /* Reset the pointer */
  432.       bufcount = 0;
  433.       }
  434.    }
  435.  
  436.  mbwrite(bufcount);    /* The final Write and we're done */
  437.  if(initfetch()==SORTERR) return(SORTERR);
  438.  return(SORTOK);
  439. }
  440.  
  441. /***********************************************************************
  442.  * MBWRITE - Write out a MERGE buffer full of tags
  443.  *   Tags are written to the final sorted file.
  444.  *
  445.  ***********************************************************************/
  446. mbwrite(unsigned tagcount)
  447. {
  448.    unsigned wsize;
  449.  
  450.    sorterror = 7;
  451.    wsize = tagsize * tagcount;
  452.    if(write(mfh, mrgbuf,wsize) != wsize) return(SORTERR);
  453.    zerobuf(mrgbuf, mbsize);        /* Zero the Merge Buffer */
  454.    return(SORTOK);
  455. }
  456.  
  457. /***********************************************************************
  458.  * BKTFILL - Fill in a sort buckt from the Sort Blocks file
  459.  ***********************************************************************/
  460. bktfill(int bnum)
  461. {
  462.    char *bptr;      /* pointer to bucket */
  463.    long *bktlptr;  /* Bucket long pointer */
  464.    long sbfpos;    /* sort block file position */
  465.  
  466.    bptr = sbuf + (bnum * bktsize);  /* Point to the bucket */
  467.  
  468.    uptr = (unsigned *) bptr;
  469.    if(*uptr > bufmax) return(SORTOK);   /* Nothing to get, this block is depleted */
  470.  
  471.    bptr += mcountsize;         /* Move block pointer to merge tag */
  472.  
  473.    sbfpos = (bnum * sbsize) + (tagsize * *uptr);  /* Calc file position */
  474.  
  475.    sorterror = 6;
  476.    if(lseek(sfh, sbfpos, 0)== -1l) return(SORTERR);
  477.    if(read(sfh, (void *)bptr, (unsigned)tagsize) != (unsigned)tagsize) return(SORTERR);
  478.  
  479.    ++*uptr;          /* Increment the counter */
  480.    return(SORTOK);
  481. }
  482. /*********************************************************************
  483.  * ZEROBUF - Fill a buffer with FF (-1)
  484.  *********************************************************************/
  485. zerobuf(char *bptr, unsigned count)
  486. {
  487.  
  488.    memset(bptr, -1, count);
  489. }
  490.